package com.scott.BinaryHeap;

import java.util.LinkedList;
import java.util.List;

/**
 * 二叉堆算法 最大堆
 * <p>
 * 二叉堆几个重要点：
 * 1:根节点索引从0开始
 * 2:若节点索引为N,则此节点的左节点索引为2N+1 右节点为2N+2
 * <p>
 * 二叉堆最大堆的特点是：
 * 添加和删除都不会改变这一特性，依然是最大的值放在第一位
 * 无论进行的删除还是添加操作，第一位的值永远是数组中最大的值
 * <p>
 * 二叉堆最小堆则正好相反
 * 二叉堆中放入的对象必须具备实现比较算法
 *
 * @author Scott 2017/11/3 14:39
 */
public class BinaryMaxHeap<T extends Comparable<T>> {

    //存放的数据列表
    private List<T> headList;


    /**
     * 构造方法
     */
    public BinaryMaxHeap() {
        headList = new LinkedList<>();
    }

    /**
     * @param t 添加值
     */
    public void add(T t) {
        //将数值插入到数组的最后一位
        headList.add(t);

        filterUp(headList.size() - 1);


    }

    /**
     * 二叉堆添加重排
     * 执行的策略：
     * 1：将插入值插入到数组的最后一位
     * 2：将数组不断的往上调整,开始位置从数组的末尾开始
     * 3：调整一直直到0，行首为止
     *
     * @param start 开始索引位置
     */
    private void filterUp(int start) {

        if (start == 0) {
            return;
        }
        //父节点下标
        int parentIndex = (start - 1) / 2;

        //当前坐标值
        T currentValue = headList.get(start);
        T parentValue = headList.get(parentIndex);

        //比较当前节点值和父节点值大小，如果当前节点值比父节点大，则调换位置，把大的往上挪
        if (currentValue.compareTo(parentValue) > 0) {
            headList.set(parentIndex, currentValue);
            headList.set(start, parentValue);

            //继续递归比较
            filterUp(parentIndex);
        }
    }

    /**
     * 删除内容
     *
     * @param t T
     * @return 删除失败 -1 删除成功 0
     */
    public int remove(T t) {
        //如果堆数组为空，则直接返回-1
        if (headList.isEmpty()) {
            return -1;
        }

        //获取待删除内容的索引位置
        int index = headList.indexOf(t);
        //如果没有找到，则直接返回-1
        if (index == -1) {
            return -1;
        }

        //将最后一个数据替换到当前位置，并将最后一位删除掉
        int size = headList.size();
        headList.set(index, headList.get(size - 1));
        headList.remove(size - 1);
        if (headList.size() > 1) {
            //进行数组的下调
            filterDown(index);
        }
        return 0;

    }

    /**
     * 最大堆的向下调整算法
     * <p>
     * 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     * <p>
     * 参数说明：
     *
     * @param index -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     */
    private void filterDown(int index) {
        //调整开始位置
        int currentIndex = index;
        //当前位置值
        T currentValue = headList.get(currentIndex);
        //左孩子位置和值
        int leftChildIndex = 2 * currentIndex + 1;
        T leftChildValue = headList.get(leftChildIndex);
        //右孩子位置和值
        int rightChildIndex = 2 * currentIndex + 2;
        T rightChildValue = headList.get(rightChildIndex);

        //将当前值比较左右孩子节点中较大的一个，将较大的那个往上调整

        if (leftChildValue.compareTo(rightChildValue) > 0) {

            headList.set(leftChildIndex, currentValue);
            headList.set(currentIndex, leftChildValue);
            filterUp(leftChildIndex);
        } else {
            headList.set(rightChildIndex, currentValue);
            headList.set(currentIndex, rightChildValue);
            filterUp(rightChildIndex);
        }

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (T aHeadList : headList) sb.append(aHeadList).append(" ");

        return sb.toString();
    }
}
